#include "../include/hash_container.h"

// ------------------------ 宏定义
#define zhi_shu_list_size 16

// ------------------------ 变量定义
/*
 *质数列表:
 *总共能存储3321-7442-8993-7538-7209个元素
 *2^64=1844-6744-0737-0955-1616*/
uint64_t zhi_shu_list[zhi_shu_list_size] = {2,  3,  5,  7,  11, 13, 17, 19,
                                            23, 29, 31, 37, 41, 43, 47, 53};

hash_tree_node_t *create_hash_tree_node(alloc_function allocator,
                                        uint8_t sub_zhishu_index, size_t size) {
  // 分配内存
  hash_tree_node_t *ret =
      (hash_tree_node_t *)allocator(sizeof(hash_tree_node_t) * size);

  // 判断内存是否分配失败
  if (ret == NULL) {
    return ret;
  }

  // 初始化各个数据的默认值
  for (int i = 0; i < size; ++i) {
    (ret + i)->data = NULL;
    (ret + i)->sub_nodes = NULL;
    (ret + i)->sub_size = 0;
    (ret + i)->sub_zhishu_index = sub_zhishu_index;
  }

  return ret;
}

void destroy_hash_tree_sub_nodes(dealloc_function deallocator,
                                 hash_tree_node_t *node) {
  if (!node || !node->sub_nodes) {
    return;
  }
  for (uint8_t i = 0; i < zhi_shu_list[node->sub_zhishu_index]; ++i) {
    destroy_hash_tree_sub_nodes(deallocator, node->sub_nodes + i);
  }
  deallocator(node->sub_nodes);
}

int8_t is_leaf(hash_tree_node_t *node) { return node->sub_size == 0; }

hash_table_tree_t *create_hash_table_tree(alloc_function allocator,
                                          dealloc_function deallocator,
                                          hash_function hash_func,
                                          compare_function comp_func,
                                          uint64_t table_size) {
  hash_table_tree_t *ret =
      (hash_table_tree_t *)allocator(sizeof(hash_table_tree_t));
  if (!ret) {
    return NULL;
  }

  ret->node = create_hash_tree_node(allocator, 0, table_size);
  if (!ret->node) {
    deallocator(ret);
    return NULL;
  }

  ret->alloc_func = allocator;
  ret->dealloc_func = deallocator;
  ret->hash_func = hash_func;
  ret->comp_func = comp_func;
  ret->size = 0;
  ret->hash_xishu = table_size;

  return ret;
}

void destroy_hash_table_tree(hash_table_tree_t *tree) {
  if (!tree) {
    return;
  }
  destroy_hash_tree_sub_nodes(tree->dealloc_func, tree->node);
  tree->dealloc_func(tree);
}

uint64_t table_hash(hash_table_tree_t *tree, void *data) {
  uint64_t hv = tree->hash_func(data);
  return hv % tree->hash_xishu;
}

void *hash_table_tree_get(hash_table_tree_t *tree, void *data) {
  if (!tree || !data) {
    return NULL;
  }

  uint64_t hash_value = tree->hash_func(data);

  hash_tree_node_t *temp = tree->node + table_hash(tree, data);
  while (temp) {
    // 比较key值
    if (tree->comp_func(temp->data, data) == 0) {
      return temp->data;
    }

    // 检测内存
    if (!temp->sub_nodes) {
      return NULL;
    }

    // 切换到下一层
    temp = temp->sub_nodes + hash_value % zhi_shu_list[temp->sub_zhishu_index];
  }

  return NULL;
}

int hash_table_tree_set(hash_table_tree_t *tree, void *data, void **pre_value) {
  if (!tree || !data) {
    return 0;
  }

  uint64_t hash_value = tree->hash_func(data);
  uint64_t temp_sub_index = 0;
  hash_tree_node_t *temp = tree->node + table_hash(tree, data);
  do {
    // 计算当前key与新key是否相同
    if (tree->comp_func(temp->data, data) == 0) {
      if (pre_value)
        *pre_value = temp->data;
      temp->data = data;
      tree->size++;
      return 1;
    }

    // 计算下一层索引
    temp_sub_index = hash_value % zhi_shu_list[temp->sub_zhishu_index];

    // 检测内存
    if (!temp->sub_nodes) {
      // 分配下一层的存储空间
      temp->sub_nodes =
          create_hash_tree_node(tree->alloc_func, temp->sub_zhishu_index + 1,
                                zhi_shu_list[temp->sub_zhishu_index]);
      // 如果内存非配失败返回
      if (!temp->sub_nodes) {
        return 0;
      }
    }

    // 如果有空位，将数据写入，如果没有，查看下一层
    if (temp->sub_nodes[temp_sub_index].data == NULL) {
      temp->sub_nodes[temp_sub_index].data = data;
      temp->sub_size++;
      tree->size++;
      return 1;
    }

    // 检查下一层
    temp = temp->sub_nodes + temp_sub_index;
  } while (temp);

  return 0;
}

void *hash_table_tree_pop(hash_table_tree_t *tree, void *data) {
  if (!tree || !data) {
    return NULL;
  }

  uint64_t hash_value = tree->hash_func(data);
  hash_tree_node_t *temp = tree->node + table_hash(tree, data);
  hash_tree_node_t *temp_father = NULL;
  int8_t temp_father_index = -1;

  // 获取该项
  while (temp) {
    // 比较key值
    if (tree->comp_func(temp->data, data) == 0) {
      break;
    }
    // 检测内存
    if (!temp->sub_nodes) {
      return NULL;
    }
    // 切换到下一层
    temp_father = temp;
    temp_father_index = hash_value % zhi_shu_list[temp->sub_zhishu_index];
    temp = temp->sub_nodes + temp_father_index;
  }

  // 暂存返回值
  void *ret = NULL;
  ret = temp->data;

  // 找到一个该项下的叶子节点
  hash_tree_node_t *temp2 = temp;
  hash_tree_node_t *temp2_father = NULL;
  int8_t temp2_father_index = -1;
  while (temp2) {
    if (temp2->sub_nodes == NULL || temp2->sub_size == 0) {
      break;
    }
    // 切换到下一层
    for (int8_t i = 0; i < zhi_shu_list[temp2->sub_zhishu_index]; ++i) {
      if (temp2->sub_nodes[i].data != NULL) {
        temp2_father = temp2;
        temp2_father_index = i;
        temp2 = temp2->sub_nodes + temp2_father_index;
        break;
      }
    }
  }

  // 要删除的目标本身不是叶子节点
  if (temp2_father != NULL) {
    // 拷贝数据
    temp->data = temp2->data;

    // 清空叶子节点数据
    temp2->data = NULL;
    temp2_father->sub_size--;

    // 如果父节点变为叶子节点，清空父节点
    if (is_leaf(temp2_father)) {
      destroy_hash_tree_sub_nodes(tree->dealloc_func, temp2_father);
    }
  } else {
    // 清空叶子节点
    temp2->data = NULL;
    tree->dealloc_func(temp2->sub_nodes);
  }

  tree->size--;

  return ret;
}

void hash_node_foreach(hash_tree_node_t *node, foreach_callback cb) {
  if (!node) {
    return;
  }
  if (node->sub_nodes) {
    for (uint8_t i = 0; i < zhi_shu_list[node->sub_zhishu_index]; ++i) {
      if ((node->sub_nodes + i)->data) {
        hash_node_foreach(node->sub_nodes + i, cb);
      }
    }
  }
  if (node->data) {
    cb(node->data);
  }
}

void hash_table_tree_foreach(hash_table_tree_t *tree, foreach_callback cb) {
  for (size_t i = 0; i < tree->hash_xishu; ++i) {
    hash_node_foreach(tree->node + i, cb);
  }
}
